import java.util.LinkedList;
import java.util.Queue;

class Solution733 {
    
    // 定义向量数组 , 方便我们找 x,y 的 上下左右 ;
    private int[] dx = {0 , 0 , 1 , -1};
    private int[] dy = {1 , -1 , 0 , 0} ;


    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
         
         int prev = image[sr][sc]  ; // 记录最开始的颜色 
         if(prev == color){
            return image ;      // 如果入口元素 就已经 等于 color , 就不需要进行 操作了
         }
        // 通过队列 ,来实现 层序遍历
        // 用一个数组 , 来记录下标
        Queue<int[]> queue = new LinkedList<>() ;
        // 放入 开始元素
        queue.add(new int[]{sr , sc}) ; 
        
        // 记录 行 列
        int m = image.length , n = image[0].length ;
        
        // 开始层序遍历
        while(!queue.isEmpty()){
             // 可以在入队列的时候, 改变颜色 , 也可以在出队列的时候改变颜色
             int[] ret = queue.poll() ;
             // 当前元素的下标
             int a = ret[0] , b = ret[1] ; 
             image[a][b] = color ;

             // 宽度优先 , 看当前元素 上下左右是否有满足条件的 , 就加入到队列里,作为下一层

            // 通过上面定义的 向量数组 , 来方便获取 当前元素的上下左右下标
            for(int i=0 ; i < 4 ; i ++){
                int x = dx[i] + a , y = dy[i]+b ;
               // 判断是否越界 && 是否 符合修改条件(和初始颜色相同
               if(x >=0 && x<m  && y>=0 && y<n && image[x][y] == prev){
                queue.add(new int[]{x , y}) ; 
               }
            } 
        }
       return image ;
    }
}